Evaluation Challenges and Directions for Information%2DSeeking Support Systems.

Deciphering mobile search patterns a study of Yahoo%21 mobile search queries.

Improving active learning recall via disjunctive boolean constraints.

Performance thresholding in practical text classification.
In practical classification, there is often a mix of learnable and unlearnable classes and only a classifier above a minimum performance threshold can be deployed. This problem is exacerbated if the training set is created by active learning. The bias of actively learned training sets makes it hard to determine whether a class has been learned. We give evidence that there is no general and efficient method for reducing the bias and correctly identifying classes that have been learned. However, we characterize a number of scenarios where active learning can succeed despite these difficulties.
Link Spam Detection Based on Mass Estimation.
Link spamming intends to mislead search engines and trigger an artificially high link-based ranking of specific target web pages. This paper introduces the concept of spam mass, a measure of the impact of link spamming on a page’s ranking. We discuss how to estimate spam mass and how the estimates can help identifying pages that benefit significantly from link spamming. In our experiments on the host-level Yahoo! web graph we use spam mass estimates to successfully identify tens of thousands of instances of heavy-weight link spamming. 1.
Automated gathering of Web information An in%2Ddepth examination of agents interacting with search engines.
this paper, we refer to spiders, softbots, meta-search applications and other automated information gathering processes all as agents
Multitasking during Web search sessions.


Efficient PageRank approximation via graph aggregation.
We present a framework for approximating random-walk based probability  distributions over Web pages using graph aggregation. We (1) partition the Web&#039;s graph into classes of quasi-equivalent vertices,  (2) project the page-based random walk to be approximated onto those classes, and (3) compute the stationary probability distribution of the resulting class-based random walk. From this distribution we can quickly reconstruct a distribution on pages. In particular, our framework can approximate the well-known PageRank distribution by setting the classes according to the set of pages on each Web host. We experimented on a Web-graph containing over 1.4 billion pages, and were able to produce a ranking that has Spearman rank-order correlation of 0.95 with respect to PageRank. A simplistic implementation of our method required less than half the running time of a highly optimized implementation of PageRank, implying that larger speedup factors are probably possible.

Internet search engines past and future.

How search engines shape the web.

A temporal comparison of AltaVista Web searching.
Major Web search engines, such as AltaVista, are essential tools in the quest to locate online information. This article reports research that used transaction log analysis to examine the characteristics and changes in AltaVista Web searching that occurred from 1998 to 2002. The research questions we examined are (1) What are the changes in AltaVista Web searching from 1998 to 2002? (2) What are the current characteristics of AltaVista searching, including the duration and frequency of search sessions? (3) What changes in the information needs of AltaVista users occurred between 1998 and 2002? The results of our research show (1) a move toward more interactivity with increases in session and query length, (2) with 70 % of session durations at 5 minutes or less, the frequency of interaction is increasing, but it is happening very quickly, and (3) a broadening range of Web searchers ’ information needs, with the most frequent terms accounting for less than 1 % of total term usage. We discuss the implications of these findings for the development of Web search engines.
Multitasking Web Search on Alta Vista.

Combating Web Spam with TrustRank.
Web spam pages use various techniques to achieve higher-than-deserved rankings in a search engine’s results. While human experts can identify spam, it is too expensive to manually evaluate a large number of pages. Instead, we propose techniques to semi-automatically separate reputable, good pages from spam. We first select a small set of seed pages to be evaluated by an expert. Once we manually identify the reputable seed pages, we use the link structure of the web to discover other pages that are likely to be good. In this paper we discuss possible ways to implement the seed selection and the discovery of good pages. We present results of experiments run on the World Wide Web indexed by AltaVista and evaluate the performance of our techniques. Our results show that we can effectively filter out spam from a significant fraction of the web, based on a good seed set of less than 200 sites. 1
Efficient pagerank approximation via graph aggregation.

The Effect of Specialized Multimedia Collections on Web Searching.

Monsters at the Gate When Softbots Visit Web Search Engine.

An analysis of multimedia searching on AltaVista.

An analysis of multimedia searching on AltaVista.



Phrase Recognition and Expansion for Short
In this paper we examine the question of query parsing for World Wide Web queries and present a novel method for phrase recognition and expansion. Given a training corpus of approximately 16 million Web queries and a handwritten context-free grammar, the EM algorithm is used to estimate the parameters of a probabilistic context-free grammar (PCFG) with a system developed by Carroll [5]. We use the PCFG to compute the most probable parse for a user query, reflecting linguistic structure and word usage of the domain being parsed. The optimal syntactic parse for a user query thus obtained is employed for phrase recognition and expansion. Phrase recognition is used to increase retrieval precision; phrase expansion is applied to make the best use possible of very short Web queries.
Exploiting Hierarchy in Text Categorization.

Metadata for Mixed%2DMedia Access.

A Comparative Study on Feature Selection in Text Categorization.
This paper is a comparative study of feature selection methods in statistical learning of text categorization. The focus is on aggressive dimensionality reduction. Five methods were evaluated, including term selection based on document frequency (DF), information gain (IG), mutual information (MI), a  Ø  2  -test (CHI), and term strength (TS). We found IG and CHI most effective in our experiments. Using IG thresholding with a knearest neighbor classifier on the Reuters corpus, removal of up to 98% removal of unique terms actually yielded an improved classification accuracy (measured by average precision) . DF thresholding performed similarly. Indeed we found strong correlations between the DF, IG and CHI values of a term. This suggests that DF thresholding, the simplest method with the lowest cost in computation, can be reliably used instead of IG or CHI when the computation of these measures are too expensive. TS compares favorably with the other methods with up to 50% vocabulary redu...
Space Optimizations for Total Ranking.

Real Life Information Retrieval Commercial Search Engines %28Panel%29.

Almost%2DConstant%2DTime Clustering of Arbitrary Corpus Subsets.
Methods exist for constant-time clustering of corpus subsets selected via Scatter/Gather browsing [3]. In this paper we expand on those techniques, giving an algorithm for almostconstant -time clustering of arbitrary corpus subsets. This algorithm is never slower than clustering the document set from scratch, and for medium-sized and large sets it is significantly faster. This algorithm is useful for clustering arbitrary subsets of large corpora --- obtained, for instance, by a boolean search --- quickly enough to be useful in an interactive setting. 1 Introduction  Document clustering has emerged as an important tool for the presentation and navigation of document collections. For example, the Scatter/Gather browsing paradigm clusters documents into topic-coherent groups and presents descriptive textual summaries to the user [2]. Informed by the summaries, the user may select clusters, thereby forming a subcollection, for iterative examination. The clustering and reclustering is done ...
Verity at TREC%2D6 Out%2Dof%2Dthe%2DBox and Beyond.

A Cooccurrence%2DBased Thesaurus and Two Applications to Information Retrieval.

Method Combination For Document Filtering.
There is strong empirical and theoretic evidence that combination of retrieval methods can improve performance. In this paper, we systematically compare combination strategies in the context of document filtering, using queries from the Tipster reference corpus. We find that simple averaging strategies do indeed improve performance, but that direct averaging of probability estimates is not the correct approach. Instead, the probability estimates must be renormalized using logistic regression on the known relevance judgements. We examine more complex combination strategies but find them less successful due to the high correlations among our filtering methods which are optimized over the same training data and employ similar document representations. 1 Introduction A text filtering system monitors an incoming document stream and selects documents identified as relevant to one or more of its query profiles. If profile interactions are ignored, this reduces to a number of independent bina...
Reexamining the Cluster Hypothesis Scatter%2FGather on Retrieval Results.
We present Scatter/Gather, a cluster-based document browsing  method, as an alternative to ranked titles for the organization and viewing of retrieval results. We systematically evaluate Scatter/Gather in this context and find significant improvements over similarity search ranking alone. This result provides evidence validating the cluster hypothesis which states that relevant documents tend to be more similar to each other than to non-relevant documents. We describe a system employing Scatter/Gather and demonstrate that users are able to use this system close to its full potential. 1 Introduction  An important service offered by an information access system is the organization of retrieval results. Conventional systems rank results based on an automatic assessment of relevance to the query [20]. Alternatives include graphical displays of interdocument similarity (e.g., [1, 22, 7]), relationship to fixed attributes (e.g., [21, 14]), and query term distribution patterns (e.g., [12]). I...
Xerox TREC%2D5 Site Report Routing%2C Filtering%2C NLP%2C and Spanish Tracks.
this report is divided into three sections. The first section describes our work on routing and filtering (Hull, Schutze, and Pedersen), the second section covers the NLP track (Grefenstette, Schulze, and Gaussier), and the final section addresses the Spanish track (Grefenstette, Schulze, and Hull). 2 Routing and Filtering
Revealing Collection Structure through Information Access Interfaces.

A Comparison of Classifiers and Document Representations for the Routing Problem.
In this paper, we compare learning techniques based on statistical classification to traditional methods of relevance feedback for the document routing problem. We consider three classification techniques which have decision rules that are derived via explicit error minimization: linear discriminant analysis, logistic regression, and neural networks. We demonstrate that the classifiers perform 1015 % better than relevance feedback via Rocchio expansion for the TREC-2 and TREC-3 routing tasks. 

Error minimization is difficult in high-dimensional feature spaces because the convergence process is slow and the models are prone to overfitting. We use two different strategies, latent semantic indexing and optimal term selection, to reduce the number of features. Our results indicate that features based on latent semantic indexing are more effective for techniques such as linear discriminant analysis and logistic regression, which have no way to protect against overfitting. Neural networks perform equally well with either set of features and can take advantage of the additional information available when both feature sets are used as input.
A Trainable Document Summarizer.
To summarize is to reduce in complexity, and hence in length, while retaining some of the essential qualities of the original. This paper focusses on document extracts, a particular kind of computed document summary.
Xerox Site Report Four TREC%2D4 Tracks.
this document sample than one would expect by chance. The terms are selected according to a binomial likelihood ratio test [10], comparing their occurrence in the first 20 documents to their occurrence in the rest of the collection. The selected terms are then weighted in proportion to  the significance of their occurrence in the sampled documents. Since it uses the baseline results, this run may also be affected by the programming error described above. query set base infl infl-np expand all Q1-25 0.454 0.484 0.492 0.467 Q26-50 0.174 0.204 0.212 0.267 20 Q1-25 0.718 0.718 0.722 0.722 Q26-50 0.306 0.354 0.378 0.402 Table 8: Average precision at all relevant docs (all) and average precision at 20 docs (20) for Spanish queries. The corrected Spanish performance figures are presented in Table 8. We include four different runs: (1) base = stop list but no morphological analysis, (2) infl = text lemmatized (stemmed) with inflectional morphology, (3) infl-np = noun phrase weight doubled, and (4) expand = query expansion. The uncorrected performance figures for infl-np and expand on Q26-50 (corresponding to our submitted runs) are 0.190/0.366 and 0.238/0.380 respectively. We present separate results for queries 1-25 (used for TREC-3) and 26-50 (used for TREC-4) since the former are substantially longer, and we note that the results reflect the difference in length. We find that lemmatization using inflectional morphology helps in most cases, making a 3-5% absolute difference in performance. However, when the queries are long and the user is examining fewer than 20 documents, there is no improvement. These conclusions agree with the results obtained for English [13], although the Spanish inflectional morphology is somewhat more effective than its English counterpart. Doubling ...
Rich Interaction in the Digital Library.
this article cross-cut a number of the usual layers of digital library architectures including retrieval engines, access protocols, intermediate services, and user inter38   Rose  Kearns  Xerox  Allaire  Hicks  Love  Magnin  Reid  Kobayashi  Adams  Chamber  Howard 3 Vairo  Montgomery  Merritt Stevens Hajia  Rosner  Galvin  Biele  Lovell  Bardsley  Rosner  Senter  Sachdav  Rosen  Carey  Male  McOi  Filt  Molin  Cut  Bun  Car  Puc  Yea  Keys  Four Ran  Mag Pit Nus Sai  Rei  Bar  Ros  Ken  Mer  Ish  Kob  Spencer  D.T. Kearns, CEO, Chairman, Chief Executive Officer 667 ---- 135  Figure 12. The Hyperbolic Tree Browser  faces. Retrieval engines need to support a much broader range of operations that allow the user to understand properties of entire collections, groups of documents, or documents themselves, thus more effectively supporting query refinement as well as other stages of the task. Access protocols and intermediate servers should provide various forms of bridge or meta-services that explicitly reveal the characteristics of the information and the mediating access mechanisms, thus allowing effective and memorable rendering of sources and their contents. Finally, the user interface should be thought of as a complete workspace in which a variety of tools are available for flexibly interacting with richly-conveyed information
A Cooccurence%2DBased. Thesaurus and two Applications on Information Retrieval.

Xerox TREC%2D3 Report Combining Exact and Fuzzy Predictors.
this report, Section 2 describes our routing experiments, Section 3 describes our ad hoc experiments, and Section 4 discusses our results and possible future experiments.
Metadata for Mixed%2DMedia Access.

Constant Interaction%2DTime Scatter%2FGather Browsing of Very Large Document Collections.
The Scatter/Gather document browsing method uses fast document clustering to produce table-of-contentslike outlines of large document collections. Previous work [1] developed linear-time document clustering algorithms to establish the feasibility of this method over moderately large collections. However, even linear-time algorithms are too slow to support interactive browsing of very large collections such as Tipster, the DARPA standard text retrieval evaluation collection. We present a scheme that supports constant interaction-time Scatter /Gather of arbitrarily large collections after nearlinear time preprocessing. This involves the construction of a cluster hierarchy. A modification of Scatter /Gather employing this scheme, and an example of its use over the Tipster collection are presented. 1 Background  Our previous work on Scatter/Gather [1] has shown that document clustering can be used as a first-class tool for browsing large text collections. Browsing is distinguished from sea...
A Practical Part%2Dof%2DSpeech Tagger.
We present an implementation of a part-of-speech tagger based on a hidden Markov model. The methodology enables robust and accurate tagging with few resource requirements. Only a lexicon and some unlabeled training text are required. Accuracy exceeds 96%. We describe implementation strategies and optimizations which result in high-speed operation. Three applications for tagging are described: phrase recognition; word sense disambiguation; and grammatical function assignment.
Scatter%2FGather A Cluster%2Dbased Approach to Browsing Large Document Collections.
Document clustering has not been well received as an information retrieval tool. Objections to its use fall into two main categories: first, that clustering is too slow for large corpora (with running time often quadratic in the number of documents); and second, that clustering does not appreciably improve retrieval. We argue that these problems arise only when clustering is used in an attempt to improve conventional search techniques. However, looking at clustering as an information access tool in its own right obviates these objections, and provides a powerful new access paradigm. We present a document browsing technique that employs document clustering as its primary operation. We also present fast (linear time) clustering algorithms which support this interactive browsing paradigm. 1 Introduction  Document clustering has been extensively investigated as a methodology for improving document search and retrieval (see [15] for an excellent review). The general assumption is that mutua...
An object%2Doriented architecture for text retrieval.
For almost all aspects of information access systems it is still the case that their optimal composition and functionality is hotly debated. Moreover, different application scenarios put different demands on individual components. It is therefore of the essence to be able to quickly build systems that permit exploration of different designs and implementation strategies. This paper presents a software implementation architecture for text retrieval systems that facilitates (a) functional modularization (b) mix-and-match combination of module implementations and (c) definition of inter-module protocols. We show how an object-oriented approach easily accommodates this type of architecture. The design principles are exemplified by code examples in Common Lisp. Taken together these code examples constitute an operational retrieval system. The design principles and protocols implemented have also been instantiated in a large scale retrieval prototype in our research laboratory. 1 Introductio...
Optimizations for Dynamic Inverted Index Maintenance.
For free-text search over rapidly evolving corpora, dynamic update of inverted indices is a basic requirement. B-trees are an effective tool in implementing such indices. The Zipfian distribution of postings suggests space and time optimizations unique to this task. In particular, we present two novel optimizations, merge update, which performs better than straight forward block update, and pulsing which significantly reduces space requirements without sacrificing performance. Inverted Indices Most standard free-text search methods in Information Retrieval (IR) can be implemented efficiently through the use of an inverted index. These include standard boolean, extended boolean, proximity, and relevance search algorithms. [7] An inverted index is a data structure that maps a word, or atomic search item, to the set of documents, or set of indexed units, that contain that word --- its postings. An individual posting may be a binary indication of the presence of that word in a document, ...
